package til.medium.magicSquare;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class UserMainCode
{
	//Assume following return types while writing the code for this question. 
    public static int output1;
    private static Queue<Point> fixQueue = new LinkedList<Point>();
    
    private static class Point {
    	private int row, col;
		public Point(int row, int col) {
			this.row = row;
			this.col = col;
		}
		public int getRow() {
			return row;
		}
		public int getCol() {
			return col;
		}
    }

    private static boolean remove(int N, int[][] values, List<Integer>[][] posValues, int r, int c, Integer n) {
		if(posValues[r][c].remove(n)) {
			if(posValues[r][c].size() == 0)
				return false;
			else if(posValues[r][c].size() == 1)
				fixQueue.add(new Point(r, c));
		}
		return true;
    }
    
    private static boolean fix(int N, int[][] values, List<Integer>[][] posValues, int r, int c) {
    	int n = posValues[r][c].get(0);
    	values[r][c] = n;
    	for(int i = 0; i < N * N; i++) {
    		// row
    		if(i != c && !remove(N, values, posValues, r, i, n))
   				return false;
    		// column
    		if(i != r && !remove(N, values, posValues, i, c, n))
   				return false;
    	}
    	int startRow = r - r % N, startCol = c - c % N;
    	int endRow = startRow + N, endCol = startCol + N; // these are start of next smaller square
    	// small square
    	for(int i = startRow; i < endRow; i++) {
    		for(int j = startCol; j < endCol; j++) {
    			if(i == r && j == c)
    				continue;
    			if(!remove(N, values, posValues, i, j, n))
    				return false;
    		}
    	}
    	// swap up
    	if(r >= N) {
    		for(int i = 0; i < startCol; i++) {
    			if(!remove(N, values, posValues, r - N, i, n))
    				return false;
    		}
    		for(int i = endCol; i < N * N; i++) {
    			if(!remove(N, values, posValues, r - N, i, n))
    				return false;
    		}
    	}
    	// swap down
    	if(r < N * N - N) {
    		for(int i = 0; i < startCol; i++) {
    			if(!remove(N, values, posValues, r + N, i, n))
    				return false;
    		}
    		for(int i = endCol; i < N * N; i++) {
    			if(!remove(N, values, posValues, r + N, i, n))
    				return false;
    		}
    	}
    	// swap left
    	if(c >= N) {
    		for(int i = 0; i < startRow; i++) {
    			if(!remove(N, values, posValues, i, c - N, n))
    				return false;
    		}
    		for(int i = endRow; i < N * N; i++) {
    			if(!remove(N, values, posValues, i, c - N, n))
    				return false;
    		}
    	}
    	// swap right
    	if(c < N * N - N) {
    		for(int i = 0; i < startRow; i++) {
    			if(!remove(N, values, posValues, i, c + N, n))
    				return false;
    		}
    		for(int i = endRow; i < N * N; i++) {
    			if(!remove(N, values, posValues, i, c + N, n))
    				return false;
    		}
    	}
    	return true;
    }
    
    private static boolean fix(int N, int[][] values, List<Integer>[][] posValues, int r, int c, Integer n) {
    	if(!posValues[r][c].contains(n))
    		return false;
    	posValues[r][c].clear();
    	posValues[r][c].add(n);
    	return fix(N, values, posValues, r, c);
    }
    
	public static void SolveMagicSquare(int N, int[][] Values)
    {
		fixQueue.clear();
		@SuppressWarnings("unchecked")
		List<Integer>[][] posValues = (List<Integer>[][])new ArrayList[N * N][N * N];
		for(int r = 0; r < N * N; r++) {
			for(int c = 0; c < N * N; c++) {
				posValues[r][c] = new ArrayList<Integer>();
				for(int n = 1; n <= N * N; n++) {
					posValues[r][c].add(n);
				}
			}
		}
		for(int r = 0; r < N * N; r++) {
			for(int c = 0; c < N * N; c++) {
				if(Values[r][c] > 0) {
					if(!fix(N, Values, posValues, r, c, Values[r][c])) {
						output1 = 0;
						return;
					}
				}
			}
		}
		if(!fix(N, Values, posValues, 0, 0, new Integer(1))) {
			output1 = 0;
			return;
		}
		while(!fixQueue.isEmpty()) {
			Point point = fixQueue.remove();
			if(!fix(N, Values, posValues, point.getRow(), point.getCol())) {
				output1 = 0;
				return;
			}
		}
		// if not all the cells are fixed find a solution
		// if finding solution fails set output1 to 0 else set to 1
		output1 = 1;
		return;
    }
	
    private static String[] splitMatchBrace(String str, char c) {
    	int s = 0;
    	Stack<Character> stk = new Stack<Character>();
    	List<String> strs = new ArrayList<String>();
    	for(int i = 0; i < str.length(); i++) {
    		if(str.charAt(i) == c && stk.isEmpty()) {
    			strs.add(str.substring(s, i));
    			s = i + 1;
    		}
    		else if(str.charAt(i) == '{' || str.charAt(i) == '(' || str.charAt(i) == '[')
    			stk.push(str.charAt(i));
    		else if(str.charAt(i) == '}' || str.charAt(i) == ')' || str.charAt(i) == ']')
    			stk.pop();
    	}
		strs.add(str.substring(s, str.length()));
    	String[] retStr = new String[strs.size()];
    	return strs.toArray(retStr);
    }
    
	public static void main(String[] args) {
		String inputs[] = {"2:{{1,0,0,0},{0,0,2,0},{0,3,0,0},{0,0,0,4}}", "2:{{1,0,0,0},{0,0,1,0},{0,1,0,0},{0,0,0,1}}"};
		for(int i = 0; i < inputs.length; i++) {
			String[] toks = inputs[i].split(":");
			int N = Integer.parseInt(toks[0]);
			String[] rows = splitMatchBrace(toks[1].substring(1, toks[1].length() - 1), ',');
			int[][] values = new int[N * N][N * N];
			for(int r = 0; r < rows.length; r++) {
				String[] cells = rows[r].substring(1, rows[r].length() - 1).split(",");
				for(int c = 0; c < cells.length; c++) {
					values[r][c] = Integer.parseInt(cells[c]);
				}
			}
			SolveMagicSquare(N, values);
			System.out.println(output1);
		}
	}
}